COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	CS306     FINAL EXAMINATION                           FALL 1985
C00012 ENDMK
C⊗;
CS306     FINAL EXAMINATION                           FALL 1985

	This take home examination is open book and notes.
Write LISP functions as follows except where something else is
requested.  Either notation may be used.  No collaboration.
Due noon Wednesday, December 11 in room 358 MJH.


1. (20 points) simplify e is the result of simplifying a Lisp term.  It does the
following simplifications.

(CAR (CONS e1 e2)) is replaced by  e1,

(CDR (CONS e1 e2)) is replaced by  e2,

(ATOM (CONS e1 e2) is replaced by NIL,

(EQUAL e e) is replaced by T,

(IF T e1 e2) is replaced by e1,

(IF NIL e1 e2) is replaced by e2,

(NOT NIL) is replaced by T.

	Thus

	simplify (IF (EQUAL (CAR (CONS (CAR Z) Y)) (CAR Z))
		     (CAR Z)
		     Z)
		= (CAR Z)


2. (25 points) supersubst[x,y,z] is the result of substituting the Lisp
expression  x  for the atom  y  in the Lisp expression  z.
However, the Lisp expressions may include LAMBDA as a variable
binder and bound occurrences are not to be substituted for.
Also bound variables in  z  are to be changed if necessary to
prevent free variables in  x  from being captured.  Use  gensym,
described in the text and in the Common Lisp manual where necesary
for this.

	Here are some examples:

supersubst[(PLUS X Y),X,(TIMES X Y)] = (TIMES (PLUS X Y) Y).

supersubst[(PLUS X Y),Z,((LAMBDA (Z) (TIMES X Z)) Z)] 
	= ((LAMBDA (Z) (TIMES X Z)) (PLUS X Y))

supersubst[(PLUS X Z),X,((LAMBDA (Z) (TIMES X Z)) Z)]
	= ((LAMBDA (G0001) (TIMES (PLUS X Z) G0001)) Z)


3. (25 points) A molecule of DNA can be represented as a list whose
elements are the atoms A,T,G, and C.  Let u and v be two such molecules.

a. dnamatch[u,v] is the longest subsequence of u that matches a subsequence
of v, where A matches T and G matches C.
Thus  dnamatch[(T A G C T A G),(T C T A T C G)] = (T A G C).

b. dnamatch1[u,v]  is the longest match with gaps of matching length where
a gap is represented by the integer giving its length.

Thus dnamatch1[(G T A G G C), (T G A G C A)] = (T 2 G C).


4. (30 points) If we use unordered lists to represent sets we have

equiv[u,v] ← contained[u,v] and contained[v,u]

contained[u,v] ← null u or member[car u,v] and contained[cdr u, v]

member[x,u] ← not null u and [equal[x,car u] or member[x,cdr u]

union[u,v] ← if null u then v
	else if member[car u,v] then union[cdr u, v]
	else cons[car u,union[cdr u,v]]

intersection[u,v] ← if null u then NIL
	else if member[car u,v] then cons[car u,intersection[cdr u, v]
	else intersection[cdr u, v]

Prove that  union  is associative and commutative where we take
equiv  for equality, e.g. prove

equiv[union[u,union[v,w]],union[union[u,v],w]] = T.

Also prove the distributive law

equiv[intersection[u,union[v,w]],union[intersection[u,v],interesection[u,w]]].